package cn.dglydrpy.study.algorithm.od;

import java.util.*;

/**
 * @author Yyy
 * @date 2024/11/7 9:27
 * @description 根据二叉树的后序遍历和中序遍历结果，输出层次遍历结果
 * 
 输入：CBEFDA CBAEDF
 输出：ABDCEF
 */
public class Od0017_BTreeCengPrint {

    public static void main(String[] args) {
        
//        printTree();
        
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String[] line1 = scanner.nextLine().split(" ");
            String postStr = line1[0];
            String midStr = line1[1];
            
            String myAnswer = myAnswer(postStr,midStr);
            System.out.println(myAnswer);
        }
    }

    private static String myAnswer(String postStr, String midStr) {
        String ans = "";

        // 整理为树
        Node root = buildBinTree(postStr,midStr);

        // 按层遍历
        doLevelTraversal(root);

        return ans;
    }

    private static Node buildBinTree(String postStr, String midStr) {
        if (postStr.length() == 0) {
            return null;
        }
        // 构建头结点
        char rootVal = postStr.charAt(postStr.length() - 1);
        Node root = new Node(String.valueOf(rootVal));
        
        // 左右两树
        int rootIndexInorder = midStr.indexOf(rootVal);
        String leftInorder = midStr.substring(0, rootIndexInorder);
        String rightInorder = midStr.substring(rootIndexInorder + 1);
        
        String leftPostorder = postStr.substring(0, leftInorder.length());
        String rightPostorder = postStr.substring(leftInorder.length(), postStr.length() - 1);
        
        root.left = buildBinTree(leftPostorder, leftInorder);
        root.right = buildBinTree(rightPostorder, rightInorder);
        return root;
    }
    
    
    
    
    

    private static void printTree() {
        Node tree = new Node("4");
        tree.left = new Node("2");
        tree.right = new Node("6");
        tree.left.left = new Node("1");
        tree.left.right = new Node("3");
        tree.right.left = new Node("5");
        tree.right.right = new Node("7");
        
        doPrintTree(tree);
        System.out.println();
        System.out.println("递归序:");
        doTraversal(tree);

        System.out.println();
        System.out.println("非递归先序:");
        doUnRecursiveTraversal(tree);

        System.out.println();
        System.out.println("按层遍历:");
        doLevelTraversal(tree);

        System.out.println();
        System.out.println("morris序:");
        doMorris(tree);
        
    }

    private static void doMorris(Node tree) {
        if(tree == null){
            return;
        }
        // 假设来到当前节点cur，开始时cur来到头节点位置
        Node cur = tree;
        Node mostRight = null;
        while(cur != null){
            // morris序
            System.out.print(cur.val);
            mostRight = cur.left;
            // 1）如果cur没有左孩子，cur向右移动(cur = cur.right)
            // 2）如果cur有左孩子，找到左子树上最右的节点mostRight：
            if(mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                // a.如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)
                if(mostRight.right == null){
                    // 先序遍历
//                    System.out.print(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                // b.如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)    
                }else{
                    mostRight.right = null;
                    // 后序遍历
//                    printEdge(cur.left);
                }
            }
//            else{
//                先序遍历
//                System.out.print(cur.val);
//            }
            
            // 中序遍历
//            System.out.print(cur.val);
            cur = cur.right;
        }
        // 后序遍历
//        printEdge(tree);
    }

    public static void printEdge(Node head) {
        Node tail = reverseEdge(head);
        Node cur = tail;
        while (cur != null) {
            System.out.print(cur.val);
            cur = cur.right;
        }
        reverseEdge(tail);
    }

    public static Node reverseEdge(Node from) {
        Node pre = null;
        Node next = null;
        while (from != null) {
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }

    private static void doLevelTraversal(Node tree) {
        if(tree == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(tree);
        while (!queue.isEmpty()){
            Node poll = queue.poll();
            System.out.print(poll.val);
            if(poll.left != null){
                queue.add(poll.left);
            }
            if(poll.right != null){
                queue.add(poll.right);
            }
        }
        
    }

    private static void doUnRecursiveTraversal(Node tree) {
        if(tree == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(tree);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            System.out.print(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }

    }

    private static void doTraversal(Node tree) {
        if(tree == null){
            return;
        }
        // 1.前序
        System.out.print(tree.val);
        doTraversal(tree.left);
        // 2.中序
        System.out.print(tree.val);
        doTraversal(tree.right);
        // 3.后序
        System.out.print(tree.val);
    }

    private static void doPrintTree(Node tree) {
        System.out.println("Binary Tree:");
        printInOrder(tree, 0, "", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "", len);
        String val = to + head.val + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "", len);
    }
    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

    private static class Node{
        private String val;
        private Node left;
        private Node right;

        public Node(String val) {
            this.val = val;
        }
        
    }
}
